﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>

using namespace std;

//判定字符是否唯一
class Solution
{
public:
    bool isUnique(string astr)
    {
        if (astr.size() > 26) return false;
        int bitset = 0;
        for (auto x : astr)
        {
            if ((bitset >> (x - 'a')) & 1 == 1) return false;
            bitset |= (1 << (x - 'a'));
        }
        return true;
    }
};

//丢失的数字
class Solution
{
public:
    int missingNumber(vector<int>& nums)
    {
        int ans = 0, n = nums.size();
        for (int i = 0; i <= n; i++) ans ^= i;
        for (auto x : nums) ans ^= x;
        return ans;
    }
};


//两整数之和
class Solution
{
public:
    int getSum(int a, int b)
    {
        while (b)
        {
            // 异或是无进位相加
            int x = a ^ b;
            int carry = (a & b) << 1;
            // 进行迭代，直到进位为0
            a = x;
            b = carry;
        }
        return a;
    }
};

//只出现一次的数字Ⅱ
class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        // 3n个0 + 0 % 3 == 0
        // 3n个1 + 1 % 3 == 1
        // 3n个0 + 1 % 3 == 1
        // 3n个1 + 0 % 3 == 0
        int ans = 0;
        for (int i = 0; i < 32; i++)
        {
            int sum = 0;
            for (auto x : nums)
                if (((x >> i) & 1) == 1) sum++;
            sum %= 3;
            if (sum) ans |= (1 << i);
        }

        return ans;
    }
};

//只出现一次的数字
class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        int ans = 0;
        for (auto x : nums) ans ^= x;
        return ans;
    }
};

//只出现一次的数字III
class Solution
{
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        int tmp = 0;
        // 将所有的数异或在⼀起
        for (auto x : nums) tmp ^= x;
        int diff = 0;
        // 找出 a，b 中⽐特位不同的那⼀位
        while (1)
        {
            if (((tmp >> diff) & 1) == 1) break;
            diff++;
        }

        int a = 0, b = 0;
        // 根据 diff 位的不同，将所有的数划分为两类来异或
        for (auto x : nums)
        {
            if (((x >> diff) & 1) == 1) a ^= x;
            else b ^= x;
        }

        return { a,b };
    }
};

//消失的两个数字
class Solution
{
public:
    vector<int> missingTwo(vector<int>& nums)
    {
        int tmp = 0;
        // 将所有的数异或在⼀起
        for (auto x : nums) tmp ^= x;
        for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;

        // 找出 a，b 中⽐特位不同的那⼀位
        int diff = 0;
        while (1)
        {
            if (((tmp >> diff) & 1) == 1) break;
            diff++;
        }

        // 根据 diff 位的不同，将所有的数划分为两类来异或
        int a = 0, b = 0;
        for (auto x : nums)
        {
            if (((x >> diff) & 1) == 1) a ^= x;
            else b ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; i++)
        {
            if (((i >> diff) & 1) == 1) a ^= i;
            else b ^= i;
        }

        return { a,b };
    }
};
int main()
{
	return 0;
}